// Copyright 2013 Daniel de Kok
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.gitee.wsl.text.dictomaton

import com.gitee.wsl.ext.list.poll
import com.gitee.wsl.ext.list.pollOrNull
import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.lang.CompactIntArray
import com.gitee.wsl.lang.bits.BitSet
import com.gitee.wsl.text.format.format
import kotlin.math.min

/**
 *
 *
 * This class is used to construct a dictionary in the form of a minimized
 * deterministic finite state automaton. This builder can create a normal
 * dictionary automaton ([Dictionary] or a perfect hash automaton
 * ([PerfectHashDictionary]).
 *
 *
 *
 * The workflow is simple:
 *
 *
 *  * Create an instance of this class.
 *  * Add character sequences in lexicographic order using [DictionaryBuilder.add].
 *  * Construct the automaton with [DictionaryBuilder.build] or
 * [DictionaryBuilder.buildPerfectHash].
 *
 *
 *
 * Construction of the automaton finalizes the build process - it is not possible to add
 * new character sequences afterwards.
 *
 *
 *
 * The following construction algorithm is used:
 *
 *
 *
 * *Incremental Construction of Minimal Acyclic Finite-State Automata*, Jan Daciuk, Bruce W. Watson,
 * Stoyan Mihov, and Robert E. Watson, 2000, Association for Computational Linguistics
 *
 *
 * @author Daniel de Kok
 */
class DictionaryBuilder {
    private val d_startState: State = State()
    private val d_register: MutableMap<State, State> = HashMap()
    private var d_prevSeq: CharSequence? = null
    private var d_nSeqs: Int = 0
    private var d_finalized: Boolean = false


    /**
     * Add a character sequence.
     *
     * @param seq The sequence.
     */
    @Throws(DictionaryBuilderException::class)
    fun add(seq: CharSequence): DictionaryBuilder {
        if (d_finalized) throw DictionaryBuilderException("Cannot add a sequence to a finalized DictionaryBuilder.")

        if (d_prevSeq != null && compareCharacterSequences(d_prevSeq!!, seq) >= 0) throw DictionaryBuilderException(
            String.format("Sequences are not added in lexicographic order: %s %s", d_prevSeq, seq)
        )

        d_prevSeq = seq

        // Traverse across the shared prefix.
        var i = 0
        var curState = d_startState
        val len: Int = seq.length
        while (i < len) {
            val nextState = curState.move(seq[i])
            if (nextState != null) curState = nextState
            else break
            i++
        }

        if (curState.hasOutgoing()) replaceOrRegisterIterative(curState)

        addSuffix(curState, seq.subSequence(i, seq.length))

        ++d_nSeqs

        return this
    }

    fun compareCharacterSequences(seq1: CharSequence, seq2: CharSequence): Int {
        val len1: Int = seq1.length
        val len2: Int = seq2.length

        var i = 0
        val len: Int = min(len1, len2)
        while (i < len) {
            val ch1: Char = seq1[i]
            val ch2: Char = seq2[i]
            if (ch1 != ch2) {
                return ch1.code - ch2.code
            }

            i++
        }

        return len1 - len2
    }

    /**
     * Add all sequences from a lexicographically sorted collection.
     *
     * @param seqs A collection of sequences.
     * @throws DictionaryBuilderException
     */
    @Throws(DictionaryBuilderException::class)
    fun addAll(seqs: Collection<CharSequence>): DictionaryBuilder {
        for (seq in seqs) add(seq)

        return this
    }


    /**
     * Create a dictionary automaton. This also finalizes the [DictionaryBuilder].
     *
     * @return A finite state dictionary.
     */
    fun build(): Dictionary {
        return build(perfectHash = false, stateSuffixes = false)
    }

    /**
     * Create a perfect hash automaton. This also finalizes the [DictionaryBuilder].
     *
     * @return A perfect hash automaton.
     */
    fun buildPerfectHash(): PerfectHashDictionary {
        return build(perfectHash = true, stateSuffixes = true) as PerfectHashDictionary
    }

    fun buildPerfectHash(stateSuffixes: Boolean): PerfectHashDictionary {
        return build(true, stateSuffixes) as PerfectHashDictionary
    }

    private fun finalizeDictionary() {
        if (!d_finalized) {
            replaceOrRegisterIterative(d_startState)
            d_finalized = true
        }
    }

    /**
     * Obtain a Graphviz dot representation of the automaton. This finalizes the
     * [DictionaryBuilder].
     *
     * @return Dot representation of the automaton.
     */
    fun toDot(): String {
        finalizeDictionary()

        val stringBuilder = StringBuilder()
        stringBuilder.append("digraph G {\n")

        val stateNumbers = numberedStates()

        // We want to traverse states a fixed order, so that the output is predictable. We
        // could also store the numbered states in a TreeMap, but State doesn't implement
        // Comparable, and I wouldn't even know what that would mean ;).
        val states = arrayOfNulls<State>(stateNumbers.size)

        for (numberedState in stateNumbers.entries)
            states[numberedState.value] = numberedState.key

        for (stateNumber in states.indices) {
            val s = states[stateNumber]!!

            if (s.isFinal) stringBuilder.append(String.format("%d [peripheries=2];\n", stateNumber))

            for (trans in s.transitions.entries) stringBuilder.append(
                String.format(
                    "%d -> %d [label=\"%c\"];\n", stateNumber,
                    stateNumbers.get(trans.value), trans.key
                )
            )
        }

        stringBuilder.append("}")

        return stringBuilder.toString()
    }

    private fun addSuffix(s: State, suffix: CharSequence) {
        var s = s
        var i = 0
        val len: Int = suffix.length
        while (i < len) {
            val newState = State()
            s.addTransition(suffix[i], newState)
            s = newState
            i++
        }

        // s is now a final state.
        s.isFinal = true
    }

    private fun build(perfectHash: Boolean, stateSuffixes: Boolean): Dictionary {
        finalizeDictionary()

        val stateNumbers = numberedStates()
        val sList = stateList(stateNumbers)

        var nTransitions = 0
        for (aSList in sList) nTransitions += aSList.transitions.size

        // First compute the offsets of each state in the transition table. Note, we need the width
        // of the number of transitions, since the pointer can be one beyond the last state (if the
        // last state is a final state without transitions).
        val offsets: CompactIntArray = CompactIntArray(sList.size, CompactIntArray.width(nTransitions))
        for (i in 1..<sList.size) offsets.set(i, offsets.get(i - 1) + sList[i - 1].transitions.size)


        // Create transition tables.
        val transChars = CharArray(nTransitions)
        val transTo: CompactIntArray = CompactIntArray(nTransitions, CompactIntArray.width(sList.size - 1))

        // Final state set.
        val finalStates: BitSet = BitSet()

        // Construct the transition table.
        for (i in sList.indices) {
            var j = 0
            for (trans in sList[i].transitions.entries) {
                transChars[offsets.get(i) + j] = trans.key
                transTo.set(offsets.get(i) + j, stateNumbers.get(trans.value)!!)
                ++j
            }

            if (sList[i].isFinal) finalStates.set(i, true)
        }

        if (perfectHash && stateSuffixes) return PerfectHashDictionaryStateCard(
            offsets,
            transChars,
            transTo,
            finalStates,
            d_nSeqs
        )
        else if (perfectHash) return PerfectHashDictionaryTransCard(offsets, transChars, transTo, finalStates, d_nSeqs)
        else
            return DictionaryImpl(offsets, transChars, transTo, finalStates, d_nSeqs)
    }

    private fun numberedStates(): MutableMap<State, Int> {
        val states = HashMap<State, Int>()

        val stateQueue/*: Queue<State?>*/ = mutableListOf<State>()
        stateQueue.add(d_startState)
        while (!stateQueue.isEmpty()) {
            val s: State = stateQueue.poll()

            if (states.containsKey(s)) continue

            states.put(s, states.size)

            for (to in s.transitions.values) stateQueue.add(to)
        }

        return states
    }

    private fun replaceOrRegisterIterative(initial: State) {
        val statePath/*: Deque<State?>*/ = mutableListOf<State>()
        val childPath/*: Deque<State?>*/ = mutableListOf<State>()

        var currentState = initial
        while (currentState.hasOutgoing()) {
            statePath.push(currentState)
            val child = currentState.lastState()!!
            childPath.push(child)
            currentState = child
        }

        require(statePath.size == childPath.size)
        while (!statePath.isEmpty()) {
            val state= statePath.pop()
            val child = childPath.pop()
            replaceOrRegister(state, child)
        }
    }

    private fun replaceOrRegister(state: State, child: State) {
        val replacement = d_register[child]
        if (replacement != null) state.setLastState(replacement)
        else d_register.put(child, child)
    }

    private fun stateList(numberedStates: Map<State, Int>): Array<State> {
        val r= arrayOfNulls<State>(numberedStates.size)

        for (numberedState in numberedStates.entries) r[numberedState.value] = numberedState.key

        return r as Array<State>
    }
}
